#include "GraphManager.h"

GraphManager::GraphManager(Graph* graph)
{
	setGraph(graph);
}

GraphManager::~GraphManager(void)
{
}

List* GraphManager::getShortestPath(string vertexFrom, string vertexTo) {
	getGraph()->setDistanceWeightMode();
	return runDijkstra(vertexFrom, vertexTo);
}

List* GraphManager::getFastestPath(string vertexFrom, string vertexTo) {
	getGraph()->setTimeWeightMode();
	return runDijkstra(vertexFrom, vertexTo);
}

List* GraphManager::runDijkstra(string vertexFrom, string vertexTo) {
	Vertex* vertex = getGraph()->getVertex(vertexFrom);
	Vertex* targetVertex = getGraph()->getVertex(vertexTo);
	if (vertex == null || targetVertex == null) {
		return null;
	}

	List* vertexList = getGraph()->getVertexList();
	// Gets size for arrays
	int n = vertexList->getSize();
	// Creates arrays
	float (*distance)[2];
	distance = new float[n][2];
	initializeDistances(distance, n);
	bool* checked = new bool[n];
	initializeChecks(checked, n);
	// Sets distance for near nodes
	for (int i = 0; i < vertex->getEdgesList()->getSize(); i++) {
		Edge* nearEdge = ((EdgeNode*)vertex->getEdgesList()->get(i))->getNodeValue();
		// Holds the weight of the connection between device i and root device of the method
		distance[getGraph()->getIndexOfVertex(getGraph()->getVertex(nearEdge->getIdTo()))][WEIGHT_COL] = getGraph()->getEdgeWeight(nearEdge);
		// Holds the index of the device whose weight is stored in the first field of the array
		distance[getGraph()->getIndexOfVertex(getGraph()->getVertex(nearEdge->getIdTo()))][VERTEX_ID_COL] = float(getGraph()->getIndexOfVertex(vertex));
	}
	if (vertex->getEdgesList()->getSize() == 0) {
		return new List();
	}
	// Sets distance for current node
	distance[getGraph()->getIndexOfVertex(vertex)][WEIGHT_COL] = 0.0;
	checked[getGraph()->getIndexOfVertex(vertex)] = true;
	// Gets if there's a better way to get to the server
	bool stop = false;
	while (notAllChecked(checked, n) && !stop) {
		Vertex* minimalVertex = getMinimalDistanceVertex(*getGraph(), checked, distance, n);
		if ( minimalVertex == NULL || targetVertex->getId().compare(minimalVertex->getId()) == 0) {
			stop = true;
		} else {
			checked[getGraph()->getIndexOfVertex(minimalVertex)] = true;
			for (int j = 0; j < minimalVertex->getEdgesList()->getSize(); j++) {
				Edge* edge = ((EdgeNode*)minimalVertex->getEdgesList()->get(j))->getNodeValue();
				Vertex* connectedVertex = getGraph()->getVertex(edge->getIdTo());
				if (checked[getGraph()->getIndexOfVertex(connectedVertex)] == false) {
					float alt = distance[getGraph()->getIndexOfVertex(minimalVertex)][WEIGHT_COL] + getGraph()->getEdgeWeight(edge);
					if (alt < distance[getGraph()->getIndexOfVertex(connectedVertex)][WEIGHT_COL] || 
							distance[getGraph()->getIndexOfVertex(connectedVertex)][WEIGHT_COL] == INF) {
						distance[getGraph()->getIndexOfVertex(connectedVertex)][WEIGHT_COL] = alt; 
						distance[getGraph()->getIndexOfVertex(connectedVertex)][VERTEX_ID_COL] = float(getGraph()->getIndexOfVertex(minimalVertex));
					}
				}
			}
		}
	}
	// Creates the routing table for the router
	List* shortestPath = new List();
	createRoutingTable(distance, targetVertex, shortestPath);
	// free memory
	delete [] distance;
	delete [] checked;

	return shortestPath;
}

bool GraphManager::notAllChecked(bool* checked, int size) {
	for (int i = 0; i < size; i++) {
		if (checked[i] == false) {
			return true;
		}
	}
	return false;
}

Vertex* GraphManager::getMinimalDistanceVertex(const Graph& graph, bool* checked, float (*distance)[2], int size) {
	List* vertexList = graph.getVertexList();
	// Save minimal length to a node, and the minimal id who did it.
	float minimalLength = INF;
	string minimalId = "";
	for (int i = 0; i < size; i++) {
		if (checked[i] == false) {
			Vertex* vertex = ((VertexNode*)vertexList->get(i))->getNodeValue();
			if ((minimalLength == INF && distance[i][WEIGHT_COL] != INF) || (minimalLength != INF && distance[i][WEIGHT_COL] < minimalLength && distance[i][WEIGHT_COL] != INF)) {
				minimalLength = distance[i][WEIGHT_COL];
				minimalId = vertex->getId();
			}

			//// if there's a shorter way to get to it, choose that node.
			//if (((distance[i][WEIGHT_COL] < minimalLength) || ((minimalLength == INF) && (distance[i][WEIGHT_COL] > 0))) && !(minimalLength > 0 && distance[i][WEIGHT_COL] == INF)) {
			//	minimalLength = distance[i][WEIGHT_COL];
			//	minimalId = vertex->getId();
			//} else {
			//	// if it's equally shorter I choose the one with lower Id
			//	if (distance[i][WEIGHT_COL] == minimalLength || (minimalId.compare("") == 0)) {
			//		minimalId = vertex->getId();
			//	}
			//}
		}
	}
	if (minimalId.compare("") == 0) {
		return NULL;
	}

	return graph.getVertex(minimalId);
}

List* GraphManager::createRoutingTable(float (*distance)[2], Vertex* targetVertex, List* shortestPastIndexes) {
	Vertex* target = targetVertex;
	VertexNode* node = new VertexNode();
	node->setNodeValue(((VertexNode*)getGraph()->getVertexList()->get(getGraph()->getIndexOfVertex(targetVertex)))->getNodeValue());
	shortestPastIndexes->add(node);
	while (distance[getGraph()->getIndexOfVertex(target)][VERTEX_ID_COL] != INF) {
		VertexNode* newNode = new VertexNode();
		int vertexIdx = int(distance[getGraph()->getIndexOfVertex(target)][VERTEX_ID_COL]);
		newNode->setNodeValue(((VertexNode*)getGraph()->getVertexList()->get(vertexIdx))->getNodeValue());
		shortestPastIndexes->add(newNode);
		target = ((VertexNode*)getGraph()->getVertexList()->get(int(distance[getGraph()->getIndexOfVertex(target)][VERTEX_ID_COL])))->getNodeValue();
	}

	return shortestPastIndexes;
}

void GraphManager::initializeChecks (bool* checked, int n) {
	for (int i = 0; i < n; i++) {
		checked[i] = false;
	}
}

void GraphManager::initializeDistances(float (*distance)[2], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			distance[i][j] = INF;
		}
	}
}

Graph* GraphManager::getGraph() const {
	return graph;
}

void GraphManager::setGraph(Graph* graph) {
	this->graph = graph;
}
